package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

import javax.sound.midi.Soundbank;

/**
 * 剑指offer-面试12
 * 打印1到最大的n位数
 * 输入数字n，按顺序打印出1到最大的n为十进制数。
 * 比如输入3，则打印出1、2、3一直到最大的3位数即999
 */
public class Mianshi12 {
    public static void main(String[] args) {
        char a = '0';
        System.out.println(a + 1);
        System.out.println((char)(a + 9));
        System.out.println((a + 1) > '0');
        System.out.println((char)('0' + 1) > '9');
        printToMaxofNDigits(2);
        System.out.println();
        printToMaxofNDigitsOffer(2);
    }

    public static void printToMaxofNDigits(int n) {
        char[] digits = new char[n];
        for (int i = 0; i < n; i++) {
            digits[i] = '0';
        }
        while (!increment(digits)) {
            printDigits(digits);
        }
    }

    public static void printToMaxofNDigitsOffer(int n) {
        if (n < 0) {
            return;
        }
        char[] digits = new char[n];
        for (int i = 0; i < 10; i++) {
            digits[0] = (char) ('0' + i);
            printToMaxofNDigitsOfferRecursive(digits, 1);
        }
    }

    private static void printToMaxofNDigitsOfferRecursive(char[] digits, int offset) {
        if (offset == digits.length) {
            printDigits(digits);
            return;
        }
        for (int i = 0; i < 10; i++) {
            digits[offset] = (char) ('0' + i);
            printToMaxofNDigitsOfferRecursive(digits, offset + 1);
        }
    }

    /**
     * 数值加1，同时返回是不是最大值
     * @param digits
     * @return
     */
    private static boolean increment(char[] digits) {
        int i = digits.length - 1;
        for (; i >= 0 ; i--) {
            digits[i] = (char)(digits[i] + 1);
            if (digits[i] > '9') {
                digits[i] = '0';
            } else {
                break;
            }
        }
        if (i < 0) {
            return true;
        }
        return false;
    }

    private static void printDigits(char[] digits) {
        int index = digits.length;
        for (int i = 0; i < digits.length; i++) {
            if (digits[i] != '0') {
                index = i;
                break;
            }
        }
        for (int i = index; i < digits.length; i++) {
            System.out.print(digits[i]);
        }
        System.out.print(" ");
    }
}
